W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
To zadanie pojawiło się równolegle na finale IX OI. Polecamy wysyłać rozwiązania do tamtego zadania, to zostanie wkrótce usunięte z serwisu.
Działanie odejmowania nie jest łączne, np. , natomiast , a zatem . Wynika stąd, że wartość wyrażenia postaci zależy od kolejności wykonywania odejmowań. Zwykle przy braku nawiasów przyjmuje się, że wykonujemy działania w kolejności od lewej do prawej, czyli wyrażenie jest równoważne wyrażeniu .
Mamy dane wyrażenie postaci:
gdzie oznacza (plus) lub (minus), a oznaczają (parami) różne zmienne. Chcemy w wyrażeniu postaci:
tak rozstawić par nawiasów, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu. Na przykład, chcąc uzyskać wyrażenie równoważne wyrażeniu:
możemy w:
rozmieścić nawiasy w następujący sposób:
.
Uwaga: Interesują nas tylko wyrażenia w pełni i poprawnie ponawiasowane. Wyrażeniem w pełni i poprawnie ponawiasowanym jest
Napisz program, który:
W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita , . Jest to liczba zmiennych w danym wyrażeniu. W każdym z kolejnych wierszy jest zapisany jeden znak, lub . W -tym wierszu zapisany jest znak występujący w danym wyrażeniu między a .
Twój program powinien zapisać w pierwszym wierszu standardowego wyjścia jedną liczbę całkowitą równą ilości różnych sposobów (modulo ), na jakie można rozstawić par nawiasów w wyrażeniu tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu.
Dla danych wejściowych:
7 - - + + - +
poprawną odpowiedzią jest:
3